λ¬Έμ
π Logic
private ArrayList<Integer> makeList(ArrayList<Integer> nowNodeList, int nowN, int nextNode) {
// μ΄λν μ μλ λ
Έλλ₯Ό μ μ₯ν 리μ€νΈ
ArrayList<Integer> nextList = new ArrayList<>();
// λ€μ λ
Έλμμ κ° μ μλ λ
Έλλ₯Ό μ μ₯, μ°κ²°λ μμ λ
Έλμ λν΄μλ§!
for (int fromNextNode : infoList.get(nextNode)) nextList.add(fromNextNode);
// ν λ
ΈλκΉμ§ μ€λλ° λ°©λ¬Ένλ λ
Έλλ€ μ€ ν λ
Έλμ μ§μ μ λ°©λ¬Έν λ
Έλλ₯Ό μ μΈνκ³ μ μ₯, DFSλ‘ λ°μ§λ©΄ λ°±νΈλνΉνλ λλ..
for (int checkNode : nowNodeList)
if (checkNode != nowN && checkNode != nextNode)
nextList.add(checkNode);
return nextList;
}
- ν λ Έλμμ κ° μ μλ λ Έλ 리μ€νΈλ₯Ό μμ±νλ ν¨μ
- μ°κ²°λ μμ λ Έλλ‘λ§ μ΄λν μ μλ κ² μλλΌ, μ§λμλ λ Έλ λν μ¬λ°©λ¬Έ κ°λ₯νκΈ°μ λ λ²μ§Έ λ°λ³΅λ¬Έμμ μ΄λ₯Ό μ²λ¦¬νλ€.
π CODE
μ½λ 보기/μ κΈ°π«
import java.util.*;
class Node {
int num;
int sheepCount;
int wolfCount;
// κ° μ μλ λ
Έλλ₯Ό μ μ₯νλ 리μ€νΈ!
ArrayList<Integer> list;
public Node(int num, int sheepCount, int wolfCount, ArrayList<Integer> list) {
this.num = num;
this.sheepCount = sheepCount;
this.wolfCount = wolfCount;
this.list = list;
}
}
class Solution {
static ArrayList<ArrayList<Integer>> infoList;
static int[] info;
public int solution(int[] info, int[][] edges) {
init(info.length, edges);
this.info = info;
return bfs();
}
private void init(int length, int[][] edges) {
infoList = new ArrayList<>();
for (int i = 0; i < length; i++)
infoList.add(new ArrayList<>());
for (int[] edge : edges) {
int n1 = edge[0];
int n2 = edge[1];
infoList.get(n1).add(n2);
}
}
private int bfs() {
Queue<Node> queue = new LinkedList<>();
queue.add(new Node(0, 1, 0, infoList.get(0)));
int max = 0;
while(!queue.isEmpty()) {
Node now = queue.poll();
int nowN = now.num;
int sheepCount = now.sheepCount;
int wolfCount = now.wolfCount;
ArrayList<Integer> nowNodeList = now.list;
if (max < sheepCount)
max = sheepCount;
// ν λ
Έλμμ κ° μ μλ λ
Έλμ λν΄ νμΈ
// nowN = 0, nextNode = {1, 8}, fromNextNode = {{2, 4}, {7, 9}}
for (int nextNode : nowNodeList) {
// μμ΄κ±°λ, λλμ μκ° μμ μλ³΄λ€ μ μ κ²½μ°
if (info[nextNode] == 0)
queue.add(new Node(nextNode, sheepCount + 1, wolfCount, makeList(nowNodeList, nowN, nextNode)));
else
if (wolfCount + 1 < sheepCount)
queue.add(new Node(nextNode, sheepCount, wolfCount + 1, makeList(nowNodeList, nowN, nextNode)));
}
}
return max;
}
private ArrayList<Integer> makeList(ArrayList<Integer> nowNodeList, int nowN, int nextNode) {
// μ΄λν μ μλ λ
Έλλ₯Ό μ μ₯ν 리μ€νΈ
ArrayList<Integer> nextList = new ArrayList<>();
// λ€μ λ
Έλμμ κ° μ μλ λ
Έλλ₯Ό μ μ₯, μ°κ²°λ μμ λ
Έλμ λν΄μλ§!
for (int fromNextNode : infoList.get(nextNode)) nextList.add(fromNextNode);
// ν λ
ΈλκΉμ§ μ€λλ° λ°©λ¬Ένλ λ
Έλλ€ μ€ ν λ
Έλμ μ§μ μ λ°©λ¬Έν λ
Έλλ₯Ό μ μΈνκ³ μ μ₯, DFSλ‘ λ°μ§λ©΄ λ°±νΈλνΉνλ λλ..
for (int checkNode : nowNodeList)
if (checkNode != nowN && checkNode != nextNode)
nextList.add(checkNode);
return nextList;
}
}
βοΈ Review
-
μ²μμλ DFSλ‘ ν΄κ²°ν΄μΌ νλ μκ°ν΄λ³΄λ€κ°, λκ° BFSλ‘ νμ΄λ³΄κ³ μΆμκ³ , μμ μμ λλμ μμ λ°λΌ μλλ λͺ» κ°λ λ ΈλλΌλ λ€μ κ° μ μλ κ²½μ°κ° λ°μνκΈ°μ μΌμ’ μ λ°±νΈλνΉ κ΅¬νμ΄ νμνλ€.
- μμ΄λμ΄λ μ‘μ μ μμμΌλ, λ€μ λ°©λ¬Έν΄μΌ νλ κ²½μ°μ λν ꡬνμ μμ΄μλ μ°Έκ³ κ° νμνλ€...
- μ°Έκ³ λ₯Ό λ³΄κ³ λμ, μ΄λ° μμ© λ¬Έμ λ₯Ό μκ° μμ νμ΄μΌ λ°μ΄λΌ μ μμ§ μμκΉ .. νλ μκ° ...